理解 React 15 的“栈调和”算法。
# 调和（Reconciliation）过程与 Diff 算法
“调和”又译为“协调”，协调过程的官方定义，藏在 React 官网对虚拟 DOM 这一概念的解释中，原文如下：
Virtual DOM 是一种编程概念。在这个概念里，UI 以一种理想化的，或者说“虚拟的”表现形式被保存于内存中，并通过如 ReactDOM 等类库使之与“真实的” DOM 同步。这一过程叫作协调（调和）。
我来划一下这段话里的重点：通过如 ReactDOM 等类库使虚拟 DOM 与“真实的” DOM 同步，这一过程叫作协调（调和）
说人话：调和指的是将虚拟 DOM映射到真实 DOM 的过程。因此严格来说，调和过程并不能和 Diff 画等号。调和是“使一致”的过程，而 Diff 是“找不同”的过程，它只是“使一致”过程中的一个环节
React 的源码结构佐证了这一点：React 从大的板块上将源码划分为了Core、Renderer和Reconciler三部分。其中Reconciler（调和器）的源码位于src/renderers/shared/stack/reconciler这个路径，调和器所做的工作是一系列的，包括组件的挂载、卸载、更新等过程，其中更新过程涉及对 Diff 算法的调用。
所以说调和 !== Diff 这个结论，是站得住脚的，如果你持有这个观点，说明你很专业
但是！在如今大众的认知里，当我们讨论调和的时候，其实就是在讨论 Diff。
这样的认知也有其合理性，因为Diff 确实是调和过程中最具代表性的一环：根据 Diff 实现形式的不同，调和过程被划分为了以 React 15 为代表的“栈调和”以及 React 16 以来的“Fiber 调和”。在实际的面试过程中，当面试官抛出 Reconciliation 相关问题时，也多半是为了了解候选人对 Diff 的掌握程度。因此在本讲中，“栈调和”指的就是 React 15 的 Diff 算法。
# Diff 策略的设计思想
在展开讲解 Diff 算法的具体逻辑之前，我们首先从整体上把握一下 Diff 的设计思想。
前面我们已经提到，Diff 算法其实就是“找不同”的过程。在计算机科学领域，要想找出两个树结构之间的不同, 传统的计算方法是通过循环递归进行树节点的一一对比, 这个过程的算法复杂度是 O (n3) 。尽管这个算法本身已经是几代程序员持续优化的结果，但对计算能力有限的浏览器来说，O (n3) 仍然意味着一场性能灾难。
具体来说，若一张页面中有 100 个节点（这样的情况在实际开发中并不少见），1003 算下来就有十万次操作了，这还只是一次 Diff 的开销；若应用规模更大一点，维护 1000 个节点，那么操作次数将会直接攀升到 10 亿的量级。
经常做算法题的人都知道，OJ 中相对理想的时间复杂度一般是 O(1) 或 O(n)。当复杂度攀升至 O(n2) 时，我们就会本能地寻求性能优化的手段，更不必说是人神共愤的 O(n3) 了！我们看不下去，React 自然也看不下去。React 团队结合设计层面的一些推导，总结了以下两个规律， 为将 O (n3) 复杂度转换成 O (n) 复杂度确立了大前提：
- 若两个组件属于同一个类型，那么它们将拥有相同的
DOM树形结构； - 处于同一层级的一组子节点，可用通过设置
key作为唯一标识，从而维持各个节点在不同渲染过程中的稳定性。
除了这两个“板上钉钉”的规律之外，还有一个和实践结合比较紧密的规律，它为 React 实现高效的 Diff 提供了灵感：DOM 节点之间的跨层级操作并不多，同层级操作是主流。
接下来我们就一起看看 React 是如何巧用这 3 个规律，打造高性能 Diff 的。
# 把握三个“要点”，图解 Diff 逻辑
对于 Diff 逻辑的拆分与解读，社区目前已经有过许多版本，不同版本的解读姿势和角度各有不同。但说到底，真正需要你把握的要点无非下面这 3 个：
Diff算法性能突破的关键点在于“分层对比”；- 类型一致的节点才有继续
Diff的必要性； key属性的设置，可以帮我们尽可能重用同一层级内的节点。
这 3 个要点各自呼应着上文的 3 个规律，我们逐个来看。
# 1. 改变时间复杂度量级的决定性思路：分层对比
结合“DOM 节点之间的跨层级操作并不多，同层级操作是主流”这一规律，React 的 Diff 过程直接放弃了跨层级的节点比较，它只针对相同层级的节点作对比，如下图所示。这样一来，只需要从上到下的一次遍历，就可以完成对整棵树的对比，这是降低复杂度量级方面的一个最重要的设计。
需要注意的是：
虽然栈调和将传统的树对比算法优化为了分层对比，但整个算法仍然是以递归的形式运转的，分层递归也是递归。
那么如果真的发生了跨层级的节点操作（比如将以 B 节点为根节点的子树从 A 节点下面移动到 C 节点下面，如下图所示）会怎样呢？很遗憾，作为“次要矛盾”，在这种情况下 React 并不能够判断出“移动”这个行为，它只能机械地认为移出子树那一层的组件消失了，对应子树需要被销毁；而移入子树的那一层新增了一个组件，需要重新为其创建一棵子树。
销毁 + 重建的代价是昂贵的，因此 React 官方也建议开发者不要做跨层级的操作，尽量保持 DOM 结构的稳定性。
# 2. 减少递归的“一刀切”策略：类型的一致性决定递归的必要性
结合“若两个组件属于同一个类型，那么它们将拥有相同的 DOM 树形结构”这一规律，我们虽不能直接反推出“不同类型的组件 DOM 结构不同”，但在大部分的情况下，这个结论都是成立的。毕竟，实际开发中遇到两个 DOM 结构完全一致、而类型不一致的组件的概率确实太低了。
React 认为，只有同类型的组件，才有进一步对比的必要性；若参与 Diff 的两个组件类型不同，那么直接放弃比较，原地替换掉旧的节点，如下图所示。只有确认组件类型相同后，React 才会在保留组件对应 DOM 树（或子树）的基础上，尝试向更深层次去 Diff
这样一来，便能够从很大程度上减少 Diff 过程中冗余的递归操作。
# 3. 重用节点的好帮手：key 属性帮 React “记住”节点
